package com.wxh.algorithm;

import java.util.Arrays;

/**
 * @ClassName: Sort
 * @Description: 排序
 * @Author wxh
 * @Date: 2020/1/8 9:53
 * @Version V1.0.0
 * @Since 1.8
 */
public class Sort {

    public static void main(String[] args) {
        // 静态初始化数组
        int[] scores = {5,3,5,2,8};
//        selectSort(scores);
//        System.out.println("选择排序："+Arrays.toString(scores));
        bubbleSort(scores);
        System.out.println("冒泡排序："+Arrays.toString(scores));

        scores = new int[]{6, 1, 2, 7, 9, 3, 4, 5, 10, 8};
        quickSort(scores, 0, scores.length - 1);
        System.out.println("快速排序："+Arrays.toString(scores));

        scores = new int[]{6, 3, 1, 7, 5, 8, 9, 2, 4};
        decryptQq(scores);
    }

    /**
     * 选择排序: 默认第一个是已经排好序的数，让第一个元素与数组剩下元素比较，依次循环
     * @param ary  需要排序的数组
     */
    public static void selectSort(int[] ary){
        int len = ary.length;
        for (int i = 0; i < len - 1; i++) {
            for (int j = i+1; j < len; j++) {
                // 外层每个元素都与内层所有元素比较
                if(ary[j] > ary[i]){
                    // 数组中元素值交换位置
                    int temp = ary[j];
                    ary[j] = ary[i];
                    ary[i] = temp;
                }
            }
        }
    }

    /**
     * 冒泡排序：外层循环控制内层两个相邻元素比较次数，内层循环比较相邻元素
     * @param ary 需要排序的数组
     */
    public static void bubbleSort(int[] ary){
        int len = ary.length;
        // 外层控制比较次数
        for (int i = 0; i < len; i++) {
            // 内层比较相邻元素
            for (int j = 0; j < len - 1 - i; j++) {
                if(ary[j+1] > ary[j]){
                    // 数组中元素值交换位置
                    int temp = ary[j+1];
                    ary[j+1] = ary[j];
                    ary[j] = temp;
                }
            }
        }
    }

    /**
     *  快速排序：将第一个元素作为基准输，大于这个元素，插入它的右边，小于插入它的左边
     * @param ary 需要排序的数组
     * @param low 最低位
     * @param high 最高位
     */
    public static void quickSort(int[] ary,int low, int high){

        // 最左边索引位置
        int i;
        // 最右边索引位置
        int j;
        // 基准位元素值
        int basePosition;
        // 临时变量，交换位置
        int temp;
        // 如果不满足条件，直接结束
        if(low > high){
            return;
        }
        i = low;
        j = high;
        // 基准元素的值
        basePosition = ary[low];
        while(i<j){
            // 先看右边，依次往左递减
            while(basePosition <= ary[j] && i<j){
                j--;
            }
            // 再看左边，依次往右递增
            while(basePosition >= ary[i] && i<j){
                i++;
            }
            // 如果满足条件则交换
            if(i<j){
                temp = ary[j];
                ary[j] = ary[i];
                ary[i] = temp;
            }
        }

        // 最后将基准为与i和j相等位置的数字交换
        ary[low] = ary[i];
        ary[i] = basePosition;

        // 递归调用左半数组
        quickSort(ary,low,j - 1);

        // 递归调用右半数组
        quickSort(ary,j + 1,high);
    }

    /**
     * 解码QQ好：将一串数字，第一个删除，第二个放入这个数字串最后一位，依次循环处理，直到删除完，
     * 得出被删除数字的顺序
     * @param ary 需要排序的数组
     */
    public static void decryptQq(int[] ary){
        int[] arr = new int[100];
        for (int i = 0; i < ary.length; i++) {
            arr[i] = ary[i];
        }
        // 队首
        int head = 0;
        // 队尾
        int tail = ary.length;
        System.out.print("解密QQ为：");
        while(head < tail){
            // 打印队首，并将队首出队,数组第一个元素
            System.out.print(arr[head]);
            head++;
            // 数组第二个元素放入队尾
            arr[tail] = arr[head];
            tail++;
            // 再将队首出队
            head++;
        }
    }

}
